class Node():
    def __init__(self,data = -1,leftPointer = -1,rightPointer = -1):
        self.data = data
        self.leftPointer = leftPointer
        self.rightPointer = rightPointer


# 1. Realize factorial of n
def factorial(num):
    if num <= 0:
        return 1
    else:
        return num * factorial(num - 1)
# 2. Calculate the result of 1+2+3+...+100
def sum(n):
    if n == 1:
        return 1
    else:
        return n + sum(n - 1)
# 3. Given an array, find the position of a number in the array
def find(num,list,index):
    if list[index] == num:
        return index
    else:
        return find(num,list,index + 1)


# 4.  Post order output binary tree
def outPut(binaryTree,currentNode):
    if currentNode == -1:
        return
    else:
        outPut(binaryTree,binaryTree[currentNode].leftPointer)
        outPut(binaryTree,binaryTree[currentNode].rightPointer)
        print(binaryTree[currentNode].data)

# 5. Complete binary search with recursive algorithm
def binarySearch(list,num,first,last):
    if first>last:
        return -1
    middle = (first + last) // 2
    if list[middle] == num:
        return middle
    elif list[middle] < num:
        first = middle + 1
        return binarySearch(list,num,first,last)
    elif list[middle] > num:
        last = middle - 1
        return binarySearch(list,num,first,last)


# 6. Fibonacci sequence outputting the nth number
def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)






if __name__ == '__main__':
    factorial = factorial(3)
    print(factorial)
    sum = sum(100)
    print(sum)
    list = [1,2,3,4,5,6]
    index = find(5,list,0)
    print(index)
    binaryTree = [Node(3, 1, 2),Node(1, -1, -1),Node(5, 3, -1),Node(4, -1, -1),Node(leftPointer=5),Node(leftPointer=-1)]
    rootPointer = 0
    freePointer = 4
    outPut(binaryTree,rootPointer)
    list2 = [1,2,3,4,5,6,7,8,9]
    pos = binarySearch(list2,9,0,len(list2)-1)
    print(pos)
    result = fibonacci(4)
    print(result)